package org.example.struct.array2;

import com.alibaba.fastjson.JSON;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * @author liyishan
 * @date 2024/5/24 11:07
 * @apiNote
 */

public class Test001673MostCompetitive {

    public static void main(String[] args) {
        int[] nums = {2, 4, 3, 3, 5, 4, 9, 6};
        int k = 4;
        int[] res = mostCompetitive(nums, k);
        System.out.println(JSON.toJSON(res));
    }

    /**
     * 超出时间限制
     * @param nums
     * @param k
     * @return
     */
    public static int[] mostCompetitive(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int prevSize = 0;
        for (int j = 0; j < k; j++) {
            int min = Integer.MAX_VALUE;
            int prev = prevSize;
            for (int i = prevSize; i <= n - (k - j); i++) {
                if (map.get(nums[i]) > 0) {
                    if(nums[i] < min){
                        min = nums[i];
                        prev = i;
                    }
                }
            }
            prevSize = prev + 1;
            res[j] = min;
            map.put(min, map.get(min) - 1);
        }
        return res;
    }

    public int[] mostCompetitive1(int[] nums, int k) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && n - i + stack.size() > k && stack.peek() > nums[i]) {
                stack.pop();
            }
            stack.push(nums[i]);
        }
        int[] res = new int[k];
        while (stack.size() > k) {
            stack.pop();
        }
        for (int i = k - 1; i >= 0; i--) {
            res[i] = stack.pop();
        }
        return res;
    }

}
